export interface INode {
    data: number;
    left: INode;
    right: INode;
}


export interface ITreeNode {
    insert: (key: any) => void; // 插入一个节点
    inOrderTraverse: () => void; // 遍历节点
    preOrderTraverse: () => void; // 遍历节点
    postOrderTraverse: () => void; // 遍历节点
    getMin: () => INode; // 获取节点最小值
    getMax: () => INode; // 获取节点中最大值
    find: (key: any) => INode; // 寻找节点
    remove: (key: any) => INode; // 删除一个节点
}

export class Node implements INode {
    data: number;
    left: INode;
    right: INode;
    root: INode;

    constructor(data: any) {
        this.data = data;
        this.root = this;
    }
}

export class BinaryTreeNode {

    root: INode;

    insertNode(data: number) {
        let newNode = new Node(data);
        const insertNode = (node: INode, newNode: INode) => {
            if (newNode.data < node.data) {
                if (!node.left) {
                    node.left = newNode
                } else {
                    insertNode(node.left, newNode);
                }
            } else {
                if (!node.right) {
                    node.right = newNode
                } else {
                    insertNode(node.right, newNode);
                }
            }
        };
        if (!!this.root) {
            insertNode(this.root, newNode)
        } else {
            this.root = newNode;
        }
    }

    inOrder() {
        let nodeDatas: number[] = [];
        const eachInNode = (nodeEl: INode, callback: (d: number) => number) => {
            if (!!nodeEl) {
                eachInNode(nodeEl.left, callback)
                nodeDatas.push(callback(nodeEl.data));
                eachInNode(nodeEl.right, callback);
            }
        };
        if (!!this.root) {
            eachInNode(this.root, (d) => d)
        }
        return nodeDatas;
    }

    forOrder() {
        let nodeDatas: number[] = [];
        const eachInNode = (nodeEl: INode, callback: (d: number) => number) => {
            if (!!nodeEl) {
                nodeDatas.push(callback(nodeEl.data))
                eachInNode(nodeEl.left, callback);
                eachInNode(nodeEl.right, callback);
            }
        };
        if (!!this.root) {
            eachInNode(this.root, (d) => d)
        }
        return nodeDatas;
    }

    endOrder() {
        let nodeDatas: number[] = [];
        const eachInNode = (nodeEl: INode, callback: (d: number) => number) => {
            if (!!nodeEl) {
                eachInNode(nodeEl.left, callback);
                eachInNode(nodeEl.right, callback);
                nodeDatas.push(callback(nodeEl.data))
            }
        };
        if (!!this.root) {
            eachInNode(this.root, (d) => d)
        }
        return nodeDatas;
    }

    find(data: number) {
        const findNode = (node: INode, d: number): any => {
            if (!node) return null;
            if (node.data == data) return node;
            return findNode(data < node.data ? node.left : node.right, d)
        };
        return findNode(this.root, data);
    }

    getMinNode(node:any = null) {
        const findMinNode = (node: INode): any => {
            return node ? node.left ? findMinNode(node.left) : node : null;
        };

        return findMinNode(node || this.root)
    }

    getMaxNode() {
        const findMinNode = (node: INode): any => {
            return node ? node.right ? findMinNode(node.right) : node : null;
        };

        return findMinNode(this.root)
    }

    remove(data: number) {
        const removeNode = (node: INode, dl: number):any => {
            if (!node) return null;
            if (dl < node.data) {
                node.left = removeNode(node.left, dl);
                return node;
            } else if (dl > node.data) {
                node.right = removeNode(node.right, dl);
                return node;
            } else  {
                debugger
                if(!node.left && !node.right) return null;
                if(!node.left) return  node.right;
                if(!node.right) return  node.left;
                if(!!node.left && !!node.right){
                    let _node = this.getMinNode(node.right);
                    node.data = _node.data;
                    node.right = removeNode(node.right, _node.data);
                    return  node;
                }
            }
        };
        return removeNode(this.root, data);
    }
}
